#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int maxValue(vector<vector<int>>& events, int k) {
        int n = events.size(), ret = events[0][2];
        sort(events.begin(), events.end(), [](vector<int>& e1, vector<int>& e2) { return e1[1] < e2[1]; });
        vector<vector<int>> dp(n + 1, vector<int>(k + 1));
        for (int i = 0; i < n; i++)
        {
            int pos = lower_bound(events.begin(), events.begin() + i, events[i][0],
                [](vector<int>& e, int lower) { return e[1] < lower; }) - events.begin();
            for (int j = 1; j <= k; j++)
                dp[i + 1][j] = max(dp[i][j], dp[pos][j - 1] + events[i][2]);
        }

        return dp[n][k];
    }
};